package solution;

import java.util.*;

class LRUCache {

    public Map<Integer, Integer> map1 = new HashMap<>();

    public Map<Integer, Integer> map2 = new HashMap<>(); // key - time

    public Integer capacity; //总容量
    public Integer usedCapacity; //已用容量

    public LRUCache(int capacity) {
        this.capacity = capacity;
        this.usedCapacity = 0;
    }

    public int get(int key) {
        Integer value = map1.get(key);
        if (null == value) {
            return -1;
        } else {
            map2.put(key, map2.getOrDefault(key, 1) + 1);
            return value;
        }
    }

    public void put(int key, int value) {
        if (usedCapacity == capacity) {
            //达到容量上限
            List<Map.Entry<Integer, Integer>> list = new ArrayList<Map.Entry<Integer, Integer>>(map2.entrySet());
            list.sort(new Comparator<Map.Entry<Integer, Integer>>() {
                @Override
                public int compare(Map.Entry<Integer, Integer> o1, Map.Entry<Integer, Integer> o2) {
                    return o1.getValue().compareTo(o2.getValue()); //从小到大排序
                }
            });
            map2.remove(list.get(0).getKey());
            map1.remove(list.get(0).getKey());
            usedCapacity--;
        }
        map1.put(key, value);
        map2.put(key, 1);
        usedCapacity++;
    }
}

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache obj = new LRUCache(capacity);
 * int param_1 = obj.get(key);
 * obj.put(key,value);
 */